package com.cet.algorithm.二叉树.二叉搜索树中的插入操作;

/**
 * @program: cet-practice
 * @description: BST中插入操作
 * @author: 陈恩涛
 * @create: 2023-04-06 19:31
 **/
public class LC701 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7));
        System.out.println(insertIntoBSTVoid(root, 5));
    }

    /**
     * 遍历BST，找到空节点插入即可
     * @param root
     * @param val
     * @return
     */
    static TreeNode insertIntoBST(TreeNode root, int val) {

        if (root == null) {
            return new TreeNode(val);
        }

        if (root.val > val) {
            root.left =  insertIntoBST(root.left, val);
        }

        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }

    static TreeNode parent;
    static TreeNode insertIntoBSTVoid(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        traversalBST(root, val);
        return root;
    }

    static void traversalBST(TreeNode root, int val) {
        if (root == null) {
            TreeNode node = new TreeNode(val);
            if (parent.val > val) {
                parent.left = node;
            } else {
                parent.right = node;
            }
            return;
        }
        parent = root;
        if (root.val > val) {
            traversalBST(root.left, val);
        }
        if (root.val < val) {
            traversalBST(root.right, val);
        }
    }

    /**
     * BST insert 迭代法
     * @param root
     * @param val
     * @return
     */
    static TreeNode insertIntoBSTIterate(TreeNode root, int val) {
        TreeNode originRoot = root;
        TreeNode insertNode = new TreeNode(val);
        if (root == null) {
            return insertNode;
        }
        TreeNode parent = null;
        while (root != null) {
            parent = root;
            if (root.val > val) {
                root = root.left;
            } else {
                root = root.right;
            }
        }

        if (parent.val > val) {
            parent.left = insertNode;
        } else {
            parent.right = insertNode;
        }
        return originRoot;
    }
}
